
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(head->next == nullptr){
            return head;
        }
        auto new_head = new ListNode(0);
        auto cur = head->next;
        auto curNext = cur->next;
        new_head->next =head;
        head->next = nullptr;
        auto newCur = head;
        while(cur)
        {
            auto front = new_head;
            auto back = front->next;
            while(back != nullptr)
            {
                if(cur->val <= back->val)
                {
                    front->next = cur;
                    cur->next = back;
                    goto end;
                }
                front = back;
                back = back->next;
            }
            newCur->next = cur;
            newCur = cur;
            newCur->next = nullptr;
            end:
            cur = curNext;
            if(cur)
            curNext = cur->next;
        }
        auto res = new_head->next;
        delete new_head;
        return res;
    }
};